package com.ujs.leetcode.FourNumCount;

import java.util.*;

/**
 * @author zhangshihao
 * @create 2023-10-16 21:20
 * 454. 四数相加 II
 * https://leetcode.cn/problems/4sum-ii/description/
 * 给你四个整数数组 nums1、nums2、nums3 和 nums4 ，数组长度都是 n ，请你计算有多少个元组 (i, j, k, l) 能满足：
 * 0 <= i, j, k, l < n
 * nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0
 */
public class FourNumCount {
    public static void main(String[] args) {
        int[] nums1 = new int[]{1, 2};
        int[] nums2 = new int[]{-2, -1};
        int[] nums3 = new int[]{-1, 2};
        int[] nums4 = new int[]{0, 2};
        int[] test = new int[]{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
        System.out.println(test.length);
        System.out.println(fourSumCount(test, test, test, test));
    }

    public static int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        int count = 0, n = nums1.length;
        // 统计nums1和nums2中数字和的值，和出现的次数
        // 计算nums3和nums4中数字的和，如果结果在map中，统计次数为 sum = sum + 1 * map出现的次数
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int key = nums1[i] + nums2[j];
                if (map.containsKey(key)) {
                    Integer value = map.get(key);
                    map.put(key, ++value);
                } else {
                    map.put(key, 1);
                }
            }
        }
        // System.out.println(map);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int temp = nums3[i] + nums4[j];
                temp = temp - 2 * temp;  // 去temp的相反数，判断是否在map中
                if (map.containsKey(temp)) {
                    count = count + map.get(temp);
                }
            }
        }
        return count;
    }
}
